import java.util.ArrayDeque;
import java.util.Deque;

/*
    @author TTDB
    @create 2025/9/4
*/
public class largestRectangleArea {
    public int largestRectangleArea(int[] heights) {
        //首先，要想找到第 i 位置最大面积是什么？
        //是以 i 为中心，向左找第一个小于 heights[i] 的位置 left_i；向右找第一个小于于 heights[i] 的位置 right_i，即最大面积为 heights[i] * (right_i - left_i -1)
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Deque<Integer> deque = new ArrayDeque<>();
        for(int i = 0; i < n; i++) {
            int h = heights[i];
            while(!deque.isEmpty() && heights[deque.peek()] >= h){
                deque.pop();
            }
            left[i] = deque.isEmpty() ? -1 : deque.peek();
            deque.push(i);
        }
        deque.clear();
        for(int i = n - 1; i >= 0; i--) {
            int h = heights[i];
            while(!deque.isEmpty() && heights[deque.peek()] >= h){
                deque.pop();
            }
            right[i] = deque.isEmpty() ? n : deque.peek();
            deque.push(i);
        }
        int res = 0;
        for(int i = 0; i < n; i++) {
            res = Math.max(res, heights[i] * (right[i] - left[i] - 1));
        }
        return res;
    }
}
